package com.chenyi.data.structure.tree;

/**
 * @author chenyi
 * @className BinarySortTree
 * @date 2022/4/24 14:10
 */
public class BinarySortTree {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int j : arr) {
            binarySortTree.add(j);
        }
        binarySortTree.infixOrder();

        System.out.println(binarySortTree.search(1));
        System.out.println(binarySortTree.searchParent(2));
    }

    Node root;

    public void add(int element) {
        if (root == null) {
            root = new Node(element);
        } else {
            root.add(new Node(element));
        }
    }

    public Integer search(int element) {
        judgeRoot();
        Node search = root.search(element);
        if (search != null) {
            return search.element;
        }
        return null;
    }

    public Integer searchParent(int element) {
        judgeRoot();
        Node searchParent = root.searchParent(element);
        if (searchParent != null) {
            return searchParent.element;
        }
        return null;
    }

    public void remove(int element) {

    }

    public void infixOrder() {
        judgeRoot();
        root.infixOrder();
    }

    public void judgeRoot() {
        if (root == null) {
            throw new RuntimeException("root is null");
        }
    }

    static class Node {
        Node left;
        Node right;
        int element;

        public Node() {
        }

        public Node(int element) {
            this.element = element;
        }

        public void add(Node node) {
            if (node.element < this.element) {
                if (this.left != null) {
                    this.left.add(node);
                } else {
                    this.left = node;
                }
            } else {
                if (this.right != null) {
                    this.right.add(node);
                } else {
                    this.right = node;
                }
            }
        }

        public Node search(int element) {
            if (this.element == element) {
                return this;
            } else if (this.element > element) {
                if (this.left != null) {
                    return this.left.search(element);
                }
                return null;
            } else {
                if (this.right != null) {
                    return this.right.search(element);
                }
                return null;
            }
        }

        public Node searchParent(int element) {
            if ((this.left != null && this.left.element == element) ||
                    (this.right != null && this.right.element == element)) {
                return this;
            } else if (this.element > element) {
                if (this.left != null) {
                    return this.left.searchParent(element);
                }
                return null;
            } else {
                if (this.right != null) {
                    return this.right.searchParent(element);
                }
                return null;
            }
        }

        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }
    }


}
